package cn.edu.njust.alg.leetcode;

import java.util.Stack;


public class Leetcode_20_valid_parentheses {

	public static boolean isValid(String s) {
		Stack<Character> stack = new Stack<Character>();
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if (c == '(' || c == '[' || c == '{') {
				stack.push(c);
			} else {
				if (c == ')') {
					if (!stack.isEmpty() && stack.peek() == '(') {
						stack.pop();
					} else {
						return false;
					}

				}
				if (c == ']') {
					if (!stack.isEmpty() && stack.peek() == '[') {
						stack.pop();
					} else {
						return false;
					}

				}
				if (c == '}') {
					if (!stack.isEmpty() && stack.peek() == '{') {
						stack.pop();
					} else {
						return false;
					}

				}
			}
		}

		return stack.isEmpty();
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] strs = { "()", "()[]{}", "(]", "([)]", "]" };
		for (String s : strs) {
			System.out.println(s + " :" + isValid(s));
		}
	}

}
